Data storage systems can often use a cache memory to speed process requests for frequently or recently accessed data. In such a system, bulk storage memory can be partitioned into addressable “blocks”. To reduce access time for blocks of data, blocks of data recently accessed in the bulk memory can be stored in a cache memory having a faster access time. A cache memory typically has a substantially smaller capacity, thus, whenever the cache memory gets close to full (or otherwise needs to remove block data for other conditions, such as aging), blocks can be removed from the cache memory to create more space. Various algorithms are known to determine which blocks of data are to be removed from a cache memory.
In some mid- to high-end disk subsystems, data can be stored in a “striped” fashion. In a striping approach, a body of data can be distributed or interleaved over multiple storage devices (e.g., disks). Such stripes can thus be partitioned into “blocks”. As but one example, an array of disks can consist of 10 k stripes, each of which can include 256 blocks, for a total of 2.56 M blocks in the entire disk array. In such a conventional approach, a cache memory can be used to store blocks of data accessed from such a disk array. At any given time, anywhere from 0 to 256 (all) blocks of a given stripe can be stored in the cache memory. In one conventional approach, for those stripes having at least one block stored within the cache memory, a count can be maintained. That is, the system can store a count value that reflects the number of blocks stored in the data cache for a given stripe.
When space in the cache memory needs to be reclaimed (e.g., to make room for new data blocks), a search can be performed to find a “stripe with maximal count”. That is, find the stripe having the largest number of its data blocks stored in the cache memory. Once found, the cached data blocks for the stripe with the highest count can be written back to the bulk storage for the stripe and then removed from the cache memory.
To better understand various features of the disclosed embodiments, a conventional data storage system will now be described with reference to FIG. 10.
A data storage system 1000 can include a number of disk storage devices 1002-0 to 1002-27FF, each of which can provide a “stripe” of data. In the particular example shown, each stripe can include 256 data blocks. Stripes of data can be accessed via an interface 1004 connected to a data/address bus 1006. The system 1000 can also include a random access memory (RAM) section 1008 and processor 1010 connected to data/address bus 1006.
A RAM section 1008 can serve as a cache memory for selected memory blocks of accessed stripes of data. In addition, in the example shown, a RAM section 1008 can also include a “heap” data structure that can maintain block tracking information.
Conventionally, a “heap” data structure can be utilized to maintain a block count value for each active stripe (i.e., each stripe having at least one data block in the cache memory). Access to a “heap” data structure typically requires a binary-tree (or similar) type search. Accordingly, for N active stripes, log2(N) steps may be required to update the data structure using a standard algorithm executed by a processor. Such steps can introduced unwanted delay into cache maintenance operations, due to the steps involved in sequentially searching through a heap type data structure. Similarly, such approaches can result in non-determinative search operations, as searching the data structure for a given block could take 1 step or log2(N) steps.
While accesses to a heap data structure can be accelerated with specialized hardware, such approaches can add unwanted complexity to the system.
Accordingly, there is need for a system and/or method that that can store count values and/or stripe values for an associated cache that provide for faster replacement operations than conventional approaches.
For example, it would be desirable that a method accomplish a cache replacement operation in a smaller number of steps. In particular, it would be desirable for the number of steps to be independent of the total number of stripes (N), as opposed to conventional method that can require N or log2(N) steps.
It would also be desirable that such a system and/or method utilize existing “off the shelf” devices, rather than specialized circuitry, and that the amount of extra hardware required, as compared to a conventional approach, is minimal.
It would further be desirable that such a system and/or method be fast and simple to implement with respect to existing designs.